package Dynamic_Programming;
/*
*
* 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
*
* 确定dp数组（dp table）以及下标的含义
    爬到i个台阶的最低花费
确定递推公式
    dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])
dp数组如何初始化
    dp[0]=0 dp[1]=0
确定遍历顺序
    从前向后
举例推导dp数组
    cost 1 100 1 1 1 100 1 1 100 1
      dp 0 0   1 2 2 3   3 4 5   5 6
    cost 10 15 20
      dp  0  0 10 15
* */
public class lc746 {
    public static void main(String[] args) {
        int[] cost=new int[]{10,15,20};
        System.out.println(minCostClimbingStairs(cost));
    }
    public static int minCostClimbingStairs(int[] cost) {
        int[] dp=new int[cost.length+1];
        dp[0]=0;
        dp[1]=0;
        for (int i = 2; i <cost.length+1 ; i++) {
            dp[i]=Math.min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
        }
        return dp[cost.length];
    }
}
